package com.gali.leetcode.day22;

import java.util.ArrayList;
import java.util.List;

/**
 * @Auther: gali
 * @Date: 2022-08-11 20:11
 * @Description:
 */
public class Solution {
     public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
    public List<Integer> inorderTraversal(TreeNode root) {
            List<Integer> list = new ArrayList<>();
            traversal(list,root);
            return list;
    }

    //动态规划
    private void traversal(List<Integer> list, TreeNode root) {
        if (root==null){
            return;
        }
        traversal(list,root.left);
        list.add(root.val);
        traversal(list,root.right);
    }

    /**
     * 不同的二叉搜索树
     * @param n
     * @return
     */
    public int numTrees(int n) {
        int[] G = new int[n + 1];
        G[0] = 1;
        G[1] = 1;
        for (int i = 2; i <= n; ++i) {
            for (int j = 1; j <= i; ++j) {
                G[i] += G[j - 1] * G[i - j];
            }
        }
        return G[n];
    }

}
